package leetcode.editor.cn.q1_300.q50;

/**
 * 双指针不对，动态规划没想出来。。。只能看答案了
 *
 *
 * @author qidi
 * @date 2021-12-31 14:20:28
 */
class Q0097_InterleavingString {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            int len1 = s1.length();
            int len2 = s2.length();
            if (len1 + len2 != s3.length()) return false;

            boolean[][] dp = new boolean[len1 + 1][len2 + 1];
            dp[0][0] = true;

            for (int i = 0; i <= len1; i++) {
                for (int j = 0; j <= len2; j++) {
                    int index = i + j - 1;
                    if (i > 0) {
                        dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(index));
                    }
                    if (j > 0) {
                        dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(index));
                    }
                }
            }
            return dp[len1][len2];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0097_InterleavingString().new Solution();
        System.out.println(solution.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
        System.out.println(solution.isInterleave("aabcc", "dbbca", "aadbbbaccc"));
    }
}